package leetcode.code1489;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	class Edge {
		int x, y;
		int w;
		int i;

		public Edge(int x, int y, int w, int i) {
			this.x = x;
			this.y = y;
			this.w = w;
			this.i = i;
		}
	}

	public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
		int len = edges.length;
		// k算法要排序，为了保存index信息
		Edge[] myEdges = new Edge[len];
		for (int i = 0; i < len; i++) {
			int[] cur = edges[i];
			myEdges[i] = new Edge(cur[0], cur[1], cur[2], i);
		}
		Arrays.sort(myEdges, (a, b) -> a.w - b.w);
		int minWay = 0;// 最小生成树权值
		UnionFind union = new UnionFind(n);
		for (int i = 0; i < len; i++) {
			Edge edge = myEdges[i];
			if (!union.isSameSet(edge.x, edge.y)) {
				minWay += edge.w;
				union.union(edge.x, edge.y);
			}
		}
		// 关键边
		List<Integer> vips1 = new ArrayList<>();
		// 伪关键边
		List<Integer> vips2 = new ArrayList<>();
		for (int i = 0; i < len; i++) {
			Edge edge = myEdges[i];
			// false myEdge中第i条边一定不要
			int cur = this.weights(len, n, myEdges, i, false);
			if (cur > minWay) {// 说明这个边不能去掉，去掉权值上去了，是关建边。
				vips1.add(edge.i);
			} else if (cur == minWay) {
				// true myEdge中第i条边一定要
				cur = this.weights(len, n, myEdges, i, true);
				if (cur == minWay) {// 仍能完成构建最小生成树，说明这个边是可以去掉，也可以要，是个伪关键边
					vips2.add(edge.i);
				}
			}
		}
		List<List<Integer>> ans = new ArrayList<>();
		ans.add(vips1);
		ans.add(vips2);
		return ans;
	}

	private int weights(int len, int n, Edge[] myEdges, int idx, boolean add) {
		UnionFind union = new UnionFind(n);
		int minWay = 0;
		if (add) {
			Edge edge = myEdges[idx];
			union.union(edge.x, edge.y);
			minWay += edge.w;
			n--;
		}
		for (int i = 0; i < len; i++) {
			if (idx == i) {
				continue;
			}
			Edge edge = myEdges[i];
			if (!union.isSameSet(edge.x, edge.y)) {
				union.union(edge.x, edge.y);
				minWay += edge.w;
				n--;
			}
		}
		return n == 1 ? minWay : Integer.MAX_VALUE;
	}

	class UnionFind {
		int[] roots;
		int[] sizes;
		int[] stack;

		public UnionFind(int n) {
			roots = new int[n];
			sizes = new int[n];
			for (int i = 0; i < n; i++) {
				roots[i] = i;
				sizes[i] = 1;
			}
			stack = new int[n];
		}

		public int findRoot(int id) {
			int root = 0;
			int p = 0;
			while ((root = roots[id]) != id) {
				stack[p++] = id;
				id = root;
			}
			while (p > 0) {
				roots[stack[--p]] = root;
			}
			return root;
		}

		public boolean isSameSet(int id1, int id2) {
			return findRoot(id1) == findRoot(id2);
		}

		public void union(int id1, int id2) {
			int p1 = this.findRoot(id1);
			int p2 = this.findRoot(id2);
			if (p1 != p2) {
				int size1 = this.sizes[p1];
				int size2 = this.sizes[p2];
				if (size1 < size2) {
					this.roots[p1] = p2;
					this.sizes[p2] = size1 + size2;
					this.sizes[p1] = 0;
				} else {
					this.roots[p2] = p1;
					this.sizes[p1] = size1 + size2;
					this.sizes[p2] = 0;
				}
			}
		}
	}

	@Override
	public void debug4() {
		this.findCriticalAndPseudoCriticalEdges(6,
				HelpDebug.str2array1("[[0,1,1],[1,2,1],[0,2,1],[2,3,4],[3,4,2],[3,5,2],[4,5,2]]"));
//		this.findCriticalAndPseudoCriticalEdges(5,H.str2array1("[[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

//		14
//		[[0,1,13],[0,2,6],[2,3,13],[3,4,4],[0,5,11],[4,6,14],[4,7,8],[2,8,6],[4,9,6],[7,10,4],[5,11,3],[6,12,7],[12,13,9],[7,13,2],[5,13,10],[0,6,4],[2,7,3],[0,7,8],[1,12,9],[10,12,11],[1,2,7],[1,3,10],[3,10,6],[6,10,4],[4,8,5],[1,13,4],[11,13,8],[2,12,10],[5,8,1],[3,7,6],[7,12,12],[1,7,9],[5,9,1],[2,13,10],[10,11,4],[3,5,10],[6,11,14],[5,12,3],[0,8,13],[8,9,1],[3,6,8],[0,3,4],[2,9,6],[0,11,4],[2,5,14],[4,11,2],[7,11,11],[1,11,6],[2,10,12],[0,13,4],[3,9,9],[4,12,3],[6,7,10],[6,8,13],[9,11,3],[1,6,2],[2,4,12],[0,10,3],[3,12,1],[3,8,12],[1,8,6],[8,13,2],[10,13,12],[9,13,11],[2,11,14],[5,10,9],[5,6,10],[2,6,9],[4,10,7],[3,13,10],[4,13,3],[3,11,9],[7,9,14],[6,9,5],[1,5,12],[4,5,3],[11,12,3],[0,4,8],[5,7,8],[9,12,13],[8,12,12],[1,10,6],[1,9,9],[7,8,9],[9,10,13],[8,11,3],[6,13,7],[0,12,10],[1,4,8],[8,10,2]]
	}

}
